Parallel Identity Testing for Skew Circuits with Big Powers and Applications

摘要

Powerful skew arithmetic circuits are introduced. These are skew arithmeticcircuits with variables, where input gates can be labelled with powers $x^n$for binary encoded numbers $n$. It is shown that polynomial identity testingfor powerful skew arithmetic circuits belongs to $\mathsf{coRNC}^2$, whichgeneralizes a corresponding result for (standard) skew circuits. Twoapplications of this result are presented: (i) Equivalence ofhigher-dimensional straight-line programs can be tested in $\mathsf{coRNC}^2$;this result is even new in the one-dimensional case, where the straight-lineprograms produce strings. (ii) The compressed word problem (or circuitevaluation problem) for certain wreath products of finitely generated abeliangroups belongs to $\mathsf{coRNC}^2$.